package uba.fi.tda.tp1.sorts;

public class MergeSort extends GenericSort{

	/**
	 * {@inheritDoc}
	 */
	@Override
	protected int[] sortMethod(int[] numbers) {
		int lenght = numbers.length;
		int[] result = new int[lenght];
		System.arraycopy(numbers, 0, result, 0, lenght);
		mergeSort(result, 0, lenght-1);
		return result;
	}

	public void mergeSort(int[] numbers, int primero, int ultimo){
		if(ultimo > primero){
			int medio = (primero + ultimo)/2;
			mergeSort(numbers, primero, medio);
			mergeSort(numbers, medio + 1, ultimo);
			merge(numbers, primero, medio, ultimo);
		}
	}
	
	public void merge(int[] numbers,int primero,int medio,int ultimo){
		int[] aux = new int[ultimo - primero + 1];
	    int i = primero; 
	    int j = medio + 1;
	    int k = 0;
	 
	    while (i <= medio && j <= ultimo) {
	        if (numbers[i] < numbers[j]) {
	            aux[k] = numbers[i];
	            ++i;
	        }
	        else {
	            aux[k] = numbers[j];
	            ++j;
	        }
	        ++k;
	    }
	 
	    while (i <= medio) {
	        aux[k] = numbers[i];
	        ++i;
	        ++k;
	    }
	 
	    while (j <= ultimo) {
	        aux[k] = numbers[j];
	        ++j;
	        ++k;
	    }
	 
	    for (int n = 0; n < aux.length; ++n) numbers[primero + n] = aux[n];
	}
}
